Skip to main content

Enumeration and limit laws of series-parallel graphs

Item Preview

texts
Enumeration and limit laws of series-parallel graphs


Published December 19, 2005
SHOW MORE


We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g\cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing $K_{2,3}$ as a minor.


Language English
Collection arxiv; additional_collections; journals

See also arXiv[arXiv]

comment
Reviews

There are no reviews yet. Be the first one to write a review.
SIMILAR ITEMS (based on metadata)
Arxiv.org
by Guillaume Chapuy; Eric Fusy; Omer Gimenez; Bojan Mohar; Marc Noy
texts
eye 20
favorite 0
comment 0
Source: http://arxiv.org/abs/1001.3628v1
Arxiv.org
by Manuel Bodirsky; Peter Jonsson; Timo von Oertzen
texts
eye 19
favorite 0
comment 0
Source: http://arxiv.org/abs/1210.0420v2
Arxiv.org
by Manuel Bodirsky; Michael Pinsker
texts
eye 18
favorite 0
comment 0
Source: http://arxiv.org/abs/1011.2894v3
Arxiv.org
by Omer Gimenez; Marc Noy
texts
eye 34
favorite 0
comment 0
Source: http://arxiv.org/abs/math/0501269v2
Arxiv.org
by Manuel Bodirsky; Michael Pinsker; Todor Tsankov
texts
eye 17
favorite 0
comment 0
Source: http://arxiv.org/abs/1012.2381v4
Arxiv.org
by Manuel Bodirsky; Victor Dalmau
texts
eye 29
favorite 0
comment 0
Source: http://arxiv.org/abs/0809.2386v3
Arxiv.org
by Manuel Bodirsky; Jan Kara
texts
eye 34
favorite 0
comment 0
Source: http://arxiv.org/abs/0805.1473v2
Arxiv.org
by Manuel Bodirsky; Mihyun Kang; Oleg Verbitsky
texts
eye 19
favorite 0
comment 0
Source: http://arxiv.org/abs/math/0607531v1
Arxiv.org
by Manuel Bodirsky; Michael Pinsker
texts
eye 27
favorite 0
comment 0
Source: http://arxiv.org/abs/1105.6073v1
Arxiv.org
by Manuel Bodirsky; Miki Hermann; Florian Richoux
texts
eye 46
favorite 0
comment 0
Source: http://arxiv.org/abs/1011.4757v2